package algotithm.leetcode.dp.hot.test42;

/**
 * @author zhouyanxiang
 * @Date 2021-02-2021/2/10-21:41
 * @URL https://leetcode-cn.com/problems/trapping-rain-water/
 * @Title 42. 接雨水
 */
public class Solution {

    public static void main(String[] args) {
        int[] height = {0,1,0,2,1,0,1,3,2,1,2,1};
        Solution solution = new Solution();
        int max = solution.trap(height);
        System.out.println(max);
    }

    public int trap(int[] height) {
        int l = 0, r = height.length - 1;
        int ans = 0;
        int leftMax = 0;
        int rightMax = 0;
        while (l < r) {
            if (height[l] <= height[r]) {
                if (leftMax <= height[l]) {
                    leftMax = height[l];
                } else {
                    ans += leftMax - height[l];
                }
                l++;
            } else {
                if (rightMax <= height[r]) {
                    rightMax = height[r];
                } else {
                    ans += rightMax - height[r];
                }
                r--;
            }
        }
        return ans;
    }

}
